/**
 * 给定一个二叉**搜索树**, 找到该树中两个指定节点的最近公共祖先。
 */


// 由二叉搜索树的性质，如果 p.val 和 q.val 都比 root.val 小，那么 p、q 肯定在 root 的左子树。

// 那问题规模就变小了，递归左子树就行。

// 如果 p.val 和 q.val 都比 root.val 大，则递归右子树。

// 其他情况，root 即为所求，不管是一个大于 root.val 一个小于 root.val，还是一个等于一个小于，还是一个等于一个大于。

// 为什么？

// 因为，只要不是 p 和 q 的值都大于（小于）root.val，即，不同处在 root 的一个子树中，就只有这三种情况：

// p 和 q 分居 root 的左右子树。
// root 就是 p，q 在 p 的子树中。
// root 就是 q，p 在 q 的子树中
// 这三种情况，p 和 q 的公共祖先都是 root。



//递归
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */

var lowestCommonAncestor = function (root, p, q) {
    if (root === null) return null
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q)
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q)
    } else {
        return root
    }
};
